Multicast communication enables simultaneous transmission of data packets between a source and select receivers (i.e., those receivers belonging to a multicast group) via a packet-switched network. Multicast data packets are forwarded to receivers through a multicast distribution tree that consists of number of network nodes. For purposes of explanation only, the term node will mean a router or a device that functions as a router, it being understood that the term node should not be limited thereto. Routers of the tree are responsible for replicating data packets at each bifurcation point (the point of the tree where branches fork). This means that only one copy of the data packets travel over any particular link in the network, making multicast distribution trees extremely efficient for distributing the same information to many receivers.
There are several different multicast protocol standards that enable multicast communication, including but not limited to Protocol Independent Multicast (PIM)-Sparse Mode (SM), which is described in Internet Engineering Task Force Request for Comments 2362 entitled “Protocol Independent Multicast-Sparse Mode: Protocol Specification,” published in June 1998, and hereby incorporated by reference in its entirety. Subsequent revisions of this specification are also incorporated herein by reference in their entirety. In PIM-SM, multicast data packets are received from one or more sources via a rendezvous point (RP). The RP then forwards the data packets to receivers via a shared distribution tree. In a sense, RPs act like meeting places for sources and receivers as will be more fully described below. Routers typically function as RPs for multicast communication, and the present invention will be described with reference to routers acting as RPs it being understood that the present invention should not be limited thereto.
PIM-SM enabled networks create shared distribution trees through which multicast data packets initially travel to new receivers of a multicast group. When creating a shared distribution tree or branch thereof, PIM-SM enabled routers (other than the RP router) initially may not know the IP address of the source or sources transmitting data. However, the routers should know the IP address of the RP router. Consider the exemplary enabled network 10 shown within FIG. 1 in which hosts (e.g., server computer systems) 12 and 14 are coupled to hosts (e.g., desktop computer systems) R1 and R2 via a network of PIM-SM enabled routers 20-36. Presume only host 14 transmits multicast data packets to receivers of a multicast group designated by the IP address G1. For purposes of explanation, PIM-SM enabled router 24 is designated as the RP for multicast group G1. Suppose host R1 seeks to join multicast group G1 as a receiver, but there is no shared distribution tree branch in existence between RP router 24 and host R1's uplink router 34 through which multicast data packets can travel to reach host R1. Host R1 can initiate a shared distribution tree branch building process by first sending an Internet Group Management Protocol (IGMP) membership report that contains G1, to uplink router 34.
Uplink router 34 receives the IGMP report, and in response router 34 creates and stores in memory an output interface list (OIL) for G1, presuming one does not already exist in router 34. As will be more described below, PIM enabled routers forward multicast data packets based on interfaces identified in OILs. Router 34 adds interface 2, the interface that received the IGMP membership report from host R1, to the OIL created for G1 so that router 34 knows to forward multicast data packets it subsequently receives to receiver R1. The uplink router 34 also performs a reverse path forwarding (RPF) check using a routing table (not shown) and the known IP address (or prefix thereof) of RP router 24. RPF checks are used in identifying the next hop PIM enabled router or the next PIM enabled router that is topologically closest to the RP. In the illustrated example, router 30 is the next hop PIM enabled router towards RP router 24. Router 34 then sends a (*, G1) Join control packet out its RPF interface to router 30 coupled thereto. The “*” is a wildcard used in PIM-SM to identify any source that is transmitting multicast data packets to receivers of the multicast group G1.
Router 30 receives the (*, G1) Join control packet and responds in similar fashion. More particularly, router 30 creates an OIL for G1, presuming one does not already exist. Interface 2, the interface of router 30 that received the (*, G1) Join control packet, is added to router 30's OIL for G1. Router 30 then performs an RPF check using the IP address of RP router 24, which in turn identifies router 26 as the next hop PIM enabled router towards the RP. Router 30 then sends a (*, G1) Join control packet out its RPF interface to upstream router 26 coupled thereto.
In general this shared distribution tree branch building process continues with upstream router towards the RP router until either a (*, G1) Join control packet reaches the RP or reaches an upstream router that has a pre-existing OIL for G1. For purposes of explanation, it will be presumed that router 26 has an existing OIL for G1. This OIL may list several interfaces (not shown) of router 26, except interface 2. As such, interface 2, the interface of router 26 that received the (*, G1) Join control packet from router 30, is added to router 26's OIL for G1. Adding interface 2 to router 26's OIL for G1 completes the construction of the shared distribution tree branch between RP router 24 and uplink router 34. Thereafter, multicast data packets can flow from the RP router 24 to host R1 via the shared distribution tree branch that includes routers 26, 30, and 34 as will be more fully described below.
Host R2 can also join multicast group G1 as a receiver in a similar fashion. More particularly, host R2 can join by first sending an IGMP membership report to uplink router 36. Uplink router 36 receives the IGMP report, and in response router 36 creates and stores in memory an OIL for G1, presuming one does not already exist. Router 36 adds interface 3, the interface that received the IGMP membership report from host R2, to the OIL it creates for G1. The uplink router 36 also performs an RPF check using the known IP address of the RP router 24. In the illustrated example, router 30 is identified as the next hop PIM enabled router towards the RP. Router 36 then sends a (*, G1) Join control packet out its RPF interface to upstream router 30 coupled thereto.
Router 30 receives the (*, G1) Join control packet from router 36 via interface 3. Router 30, however, has an existing OIL for G1 as a result of the shared distribution tree branch building process described above. Interface 3, the interface of router 30 that received the (*, G1) Join control packet from router 36, is added to the OIL for G1. Accordingly, router 30's OIL for multicast group G1 will have at least two interfaces (i.e., interfaces 2 and 3). Adding interface 3 to RP router 30's OIL for G1 completes the construction of the shared distribution tree branch between router 30 and uplink router 36 since router 30 had a forwarding state (i.e., an OIL) for multicast group G1 when it received the (*, G1) Join control packet. Thereafter, multicast data packets can flow from the RP router 24 to host R1 via the shared distribution tree branch that includes routers 30 and 36 as will be more fully described below.
Source S2 transmits multicast data packets to RP router 24 for subsequent distribution to receivers R1 and R2 via the shared distribution tree. Each multicast data packet from source 14 will include G1 and S2, where S2 is the IP address of source 14. When a router including the RP router on a shared distribution tree receives a multicast data packet, the router decides which way to send it based on the router's OIL for the group destination IP address contained in the multicast packet. It is noted that a downstream router may decide which way to send the multicast packet based on other information of the packet, such as the packet's source IP address. However, since FIG. 1 is being described with reference to only source 14 transmitting multicast data packets to receivers of group G1, the routers need only use G1 to decide which way to forward multicast data packets.
Router 24 accesses its OIL for multicast group G1 in response to receiving the multicast packets from source 14. The OIL lists interface 3 as at least one output for the received multicast data packets. Accordingly, RP router 24 transmits the multicast data packets it receives, or replications thereof, from source S2 out of interface 3 to router 26. Router 26 also forwards the multicast data packets it receives, or replications thereof, from RP router 24 out of interface 2, the interface identified in the OIL for multicast group G1, to router 30. Router 30 receives the multicast packets from router 26 and accesses its OIL for G1, the destination address of the multicast data packets. When an OIL identifies more than one output interface through which multicast data packets are to be forwarded, the router replicates the multicast data packets it receives accordingly. The OIL of router 30 lists at least two output interfaces, and accordingly, router forwards replications of multicast data packets from router 26 to routers 34 and 36, respectively, via interfaces 2 and 3, respectively. For purposes of explanation, it will be presumed that router 30's OIL for G1 includes more than one interface. Lastly, routers 34 and 36 forward the multicast packets they receive from router 30 to receivers R1 and R2, respectively.
Shared distribution trees may not be the fastest or most efficient data communication path for transmitting multicast data packets from sources to receivers. After a receiver begins receiving multicast data packets from a source via the shared distribution tree as described above, the receiver's uplink router may trigger a routine to create or join a faster and/or more efficient source distribution tree. Source distribution trees, like shared distribution trees, transmit multicast packets from a source to receivers of a multicast group. Source distribution trees, however, generally avoid transmission through RPs. Packet travel time through shared distribution trees are usually higher when compared to the packet travel time through shared distribution trees since, in general, source distribution trees employ fewer routers in the communication paths between the source and receivers.
The process of creating a source distribution tree or branch thereof is similar to the process described above for creating a shared distribution tree or branch thereof. One difference, however, is that the uplink router that triggers the source tree creation initially will know the IP address of the source of interest since the uplink router has received multicast data packets containing the IP address (e.g., S2) of the source. To illustrate, suppose router 36 seeks to join a source distribution tree rooted at source 14 after router 36 receives multicast data packets from source 14 via the shared distribution tree. Router 36 creates an OIL for (S2, G2), wherein S2 is the IP address of source 14. The interface (e.g., interface 3) coupled to receiver R2 is added to the OIL for (S2, G2). Router 36 then performs an RPF check using S2 in order to identify the next hop PIM enabled router closest to source 14. In the illustrated example, router 32 as the next hop PIM enabled router towards source 14. The uplink router then sends a (S2, G2) Join control packet out the RPF interface to upstream router 32.
Router 32 receives the (S2, G2) Join control packet and creates an OIL for (S2, G2), assuming one does not previously exist. Interface 2, the interface of router 32 that received the (S2, G2) Join control packet, is added to router 32's OIL for (S2, G2). Router 32 then performs an RPF check using S2, the IP address of source 14. The RPF check identifies router 28 as the next hop PIM enabled router towards source 14. Router 32 then sends a (S2, G2) Join control packet out its RPF interface to upstream router 28 coupled thereto.
The source distribution tree branch building process is similar to the shared distribution tree branch building process in that the source distribution tree branch building process continues with each upstream router until either the (S2, G2) Join control packet reaches the root router (e.g., router 22) or an upstream router that has a pre-existing OIL for (S2, G2). For purposes of explanation, it will be presumed that router 28 has an existing OIL for (S2, G2). This OIL may list several interfaces (not shown), except interface 2. As such, interface 2, the interface of router 28 that received the (S2, G2) Join control packet from router 32, is added to router 28's OIL for (S2, G2). Adding interface 2 to router 28's OIL for (S2, G2) completes the construction of the source distribution tree branch between root router 222 and uplink router 36. Thereafter, multicast data packets can flow from source 14 to host R2 via the source distribution tree branch that includes routers 22, 28, 32 and 36.
After creation of the source distribution tree branch described above, the uplink router 36 may receive copies of data from source 14 via both the shared and source distribution trees. To avoid receiving and processing duplicate data, router 36 can send a Prune control packet to router 30 of the shared distribution tree. The Prune control packet instructs router 30 to prune off or remove the branch of the shared distribution tree for multicast group G1 that forwards multicast data packets from source S2 to router 36. This can be done by removing interface 3 from router 30's OIL for G1. Once the Prune control packet is implemented at router 30, router 36 will only receive multicast data packets from source 14 via the source distribution tree.
Packet-switched networks employing PIM-SM are widely used, but other technologies also exist for transmitting data from sources to receivers. Multiprotocol Label Switching (MPLS) is another network technology for transmitting data packets from sources to receivers. In operation, packets incoming to an MPLS network are assigned a label by an ingress label switch router (LSR). Labeled packets are forwarded along a label switch path (LSP) where each LSR makes packet forwarding decisions based solely on the contents of the label. LSPs come in several forms: point-to-point (P2P) LSPs in which labeled packets are transmitted from one ingress LSR to one egress LSR; point-to-multipoint (P2MP) LSPs in which labeled packets are transmitted from one ingress LSR to multiple egress LSRs, and; multipoint-to-multipoint (M2MP) LSPs which couple multiple ingress LSRs to multiple egress LSRs. U.S. patent application Ser. No. 11/204,837, entitled “Building Multipoint to Multipoint Label Switch Pass,” filed on Aug. 16, 2005, is incorporated herein by reference in its entirety and describes one method for building P2MP or MP2MP LSPs within an MPLS enabled network.
LSRs along an LSP use label look-up tables that link incoming packet labels to outgoing packet labels and outgoing interfaces. Each LSR strips off the incoming packet label and applies an outgoing packet label which tells the next LSR in the LSP how to forward the data packet. After stripping off the incoming packet label, branching LSRs in P2MP and MP2MP LSPs replicate packets as needed and forward the original and replicated packets to the next LSR in the LSP with the same outgoing packet label attached or added thereto. MPLS allows LSRs to make simple forwarding decisions based on the contents of a simple label, rather than making a complex forwarding decision based on an IP address (e.g., a multicast group IP address).
Labels are short, fixed length, locally significant identifiers which are used to identify a Forwarding Equivalence Class (FEC). An FEC represents packets that share the same requirement for transport, e.g., over the same path with the same forwarding treatment. Typically packets belonging to the same FEC (e.g., multicast data packets with the same source and group IP addresses S and G, respectively) will follow the same LSP through the MPLS network. While assigning a packet to an FEC, the ingress LSR may look at the IP header and also some other information such as the interface on which the packet arrived.
LSPs are provisioned using Label Distribution Protocols (LDPs) such as RSVP-TE or (M)LDP. Either of these protocols is used to establish an LSP through an MPLS network and will reserve necessary resources to meet pre-defined service requirements for the LSP. LDP lets an LSR distribute labels to its LDP peers. When an LSR assigns a label to an FEC it informs its relevant peers of this label and its meaning, and LDP is used for this purpose. Since a set of labels from an ingress LSR to an egress LSR in an MPLS network defines an LSP, LDP helps in establishing a LSP by using a set of procedures to distribute the labels among the LSR peers.
Oftentimes, multicast data packets must travel through routers that are PIM-SM enabled and routers that are MPLS enabled. Source and shared distribution trees can be formed only through those routers that are PIM enabled. While edge (i.e., ingress and egress) routers of an MPLS network may be PIM enabled, core routers are not PIM enabled. Thus, source or shared distribution trees cannot be formed through MPLS networks. However, P2MP LSPs within a MPLS network can be used to “connect” multicast group receivers on one side of an MPLS network to a source or a shared distribution tree on the other side of the MPLS network, so that multicast packets transmitted on the source or shared distribution tree can reach the receivers notwithstanding a distribution tree branch interruption caused by the MPLS network. In other words, a P2MP LSP can be used in an MPLS network to emulate a source or shared distribution tree within an MPLS network.
To illustrate, FIG. 2 shows the network 10 of FIG. 1 with PIM-SM enabled routers 26-36 replaced with MPLS enabled routers 40-52, respectively. Collectively, MPLS enabled routers 40-52 form an MPLS network 54. In addition to being MPLS enabled, routers 40, 42, 50 and 42 are PIM-SM enabled. Routers 40, 42, 50 and 42 are edge routers (e.g., ingress or egress routers), while routers 44 and 46 are core routers. Routers 44 and 46 are considered core routers since they are only capable of communicating with the egress routers 40, 42, 50 and 52 using MPLS protocols. Edge routers 40, 42, 50 and 42 can communicate with each other using, for example PIM control packets transmitted to each other vis-à-vis LSPs through core routers 44 or 46, and edge routers 40 and 42 can communicate with PIM enabled routers 22 and 24 using PIM procedures described above.
Receivers R1 and R2 can receive (S2, G1) multicast data packets via RP router 24 and a P2MP LSP consisting of routers 40, 44, 50, and 52. More particularly, ingress router 40 receives a (S2, G1) multicast data packet from RP router 24. Ingress router 40 identifies the FEC corresponding to (S2, G1) of the incoming multicast data packet from RP router 24. The FEC is then used to identify the outgoing packet label and outgoing interface (i.e., interface 2) of ingress router 40 for forwarding a labeled packet along the P2MP LSP. The outgoing packet label is attached or added to the incoming multicast data packet, and the outgoing label packet sent to core router 44, the next router of the P2MP LSP, via interface 2. Core router 44, in turn, strips off the incoming packet label from the labeled packet received from ingress router 40, and core router 44 uses the incoming packet label to look up the outgoing packet label and the outgoing interfaces. Core router 44 attaches or adds the outgoing packet label to the multicast data packet. Core router 44 replicates the outgoing labeled packet since the P2MP LSP branches out at core router 44, and the outgoing labeled packets are sent out interfaces 2 and 3 to egress routers 50 and 52, respectively, of the P2MP LSP. Egress routers 50 and 52 receive respective incoming labeled packets from core router 44. Egress routers 50 and 52 strip off the labels. As noted above, egress routers 50 and 52 are also PIM-SM enabled. As such, egress routers 50 and 54 use the multicast group address G1 contained in the multicast packets and their respective OILs for G1 to forward the multicast data packets to receivers R1 and R2, respectively.
Like the PIM-SM enabled network 10 in FIG. 1, transmission of multicast data packets from host 14 to, for example, receiver R2 in FIG. 2 is more efficiently handled by avoiding the RP router 24. Since egress router 52 is PIM-SM enabled, egress router 52 may trigger a routine to create or join a faster and/or more efficient source distribution tree after egress router 52 begins receiving (S2, G1) multicast data packets via the P2MP LSP. A source distribution tree cannot be established through MPLS network 54, but an LSP through MPLS network 54 can be used to connect egress router 52 to the source distribution tree rooted at router 22. For example, egress router 52 can receive (S2, G2) multicast data packets from host 14 via a P2MP LSP consisting of MPLS enabled routers 42, 46, and 52.
As was the case with router 36 in FIG. 1, router 52 will receive copies of data from host 14 via both the shared and source distribution trees and the P2MP and P2P LSPs, respectively. To avoid receiving duplicate data, egress router 52 ideally would send a Prune control packet to core router 44 asking it to stop sending labeled (S1, G1) multicast data packets if core router 44 was PIM enabled. Core router 46, however is not PIM enabled, and would ignore the Prune control packet from egress router 52 if egress router 52 sent it the control packet. Ingress router 40, however, is PIM enabled and is a router on the shared distribution tree rooted at RP router 24. Egress router 52 can send the Prune control packet to ingress router 40 via an LSP. In response to receiving the Prune control packet from egress router 52, ingress router 40 could end transmission of (S1, G1) multicast data packets via the P2MP LSP described above, thereby effectively pruning off egress router 52 from the shared distribution tree rooted at RP router 24. Unfortunately, if ingress router 40 ends transmission of (S1, G1) multicast data packets via the P2MP LSP described above, receiver R1 would no longer receive (S2, G1) multicast packets via egress router 50 and the P2MP LSP. Thus, egress router 52 must continue to receive duplicate data from host 14 via the P2MP LSP created to emulate the shared distribution tree and via the P2MP LSP created to emulate the source distribution tree rooted at host 14.